// https://www.lintcode.com/problem/minimum-window-substring/

public class Solution {
    /**
     * @param source : A string
     * @param target: A string
     * @return: A string denote the minimum window, return "" if there is no such a string
     */
    public String minWindow(String source , String target) {
        // write your code here
        int[] s_status = new int[256]; // 如果匹配，那么s对应字符出现的次数不应小于target对应字符出现的次数。
        int[] t_status = new int[256];
        Arrays.fill(s_status, 0);
        Arrays.fill(t_status, 0);
        int tlen = target.length();
        for (int i = 0; i < tlen; ++i) {
            ++t_status[target.charAt(i)];
        }
        int start = 0;
        int window = Integer.MAX_VALUE; // 初始窗口大小，因为要找最短，所以设了一个最大值。
        int matched = 0; // 匹配字符数
        int j = 0; // 索引位置
        for (int i = 0; i < source.length(); ++i) {
            Character c = source.charAt(i);
            if (matched < tlen) { // 没有匹配到位
                if (s_status[c] < t_status[c]) {
                    ++matched;
                }
                ++s_status[c];
            }
            if (matched == tlen) { // 匹配数够了，因为要最短，可以看下能删除哪些。
                Character cj;
                while (j < i) {
                    cj = source.charAt(j);
                    if (s_status[cj] > t_status[cj]) {
                        --s_status[cj];
                        ++j;
                    } else {
                        break;
                    }
                }
                // 调整窗口大小
                if (window > (i - j + 1)) {
                    window = i - j + 1;
                    start = j; // 前面完全没用的都可以删了
                }
                while ((j < i) && (matched == tlen)) { // 继续处理，知道再多删一个导致matched不满足。
                    cj = source.charAt(j);
                    --s_status[cj];
                    if (s_status[cj] < t_status[cj]) {
                        --matched;
                    }
                    ++j; // 跳过删除的元素
                }
            }
        }
        return (window != Integer.MAX_VALUE) ? source.substring(start, start + window) : "";
    }
}